package com.gorkr.labuladong.data_struct.bt;

import org.junit.jupiter.api.Test;

import java.util.Objects;

/**
 * @author gorkr
 * @date 2022/08/07 11:14
 **/
public class H297SerializeAndDeserializeBinaryTree {

    class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private StringBuilder sb = new StringBuilder();

    private void serializeDfs(TreeNode root) {
        // 前序遍历位置
        if (root == null) {
            sb.append("_");
            sb.append(",");
            return;
        }
        sb.append(root.val);
        sb.append(",");

        serializeDfs(root.left);
        serializeDfs(root.right);
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // 清空sb
        sb.setLength(0);
        serializeDfs(root);
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        index=0;
        String[] split = data.split(",");
        return deserializeDfs(split);
    }

    private int index = 0;
    public TreeNode deserializeDfs(String[] split){
        if(index>=split.length){
            return null;
        }
        TreeNode cur = null;
        if(Objects.equals(split[index], "_")){
            ++index;
            return null;
        }else {
            cur = new TreeNode(Integer.parseInt(split[index]));
        }
        index++;
        cur.left = deserializeDfs(split);
        cur.right = deserializeDfs(split);
        return cur;
    }

    @Test
    public void test(){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        String serialize = serialize(root);

        System.out.println(serialize);

        TreeNode deserialize = deserialize(serialize);
        System.out.println(deserialize);


    }


}
    